package Offer53_34;

/**
 * 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。
 * 在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test_53_two {
    public static void main(String[] args) {
        int[] nums = new int[]{0,1,3,4,5,6};
        System.out.println(new SolutionMissingNumber().missingNumber(nums));
        System.out.println(new SolutionMissingNumberOffer().missingNumber(nums));
        System.out.println(new SolutionMyThinking().missingNumber(nums));
    }
}

/*利用二分查找来解决
* 因为是有序数组，所以nums[mid]对应的就是mid
* 利用这个思路来进行求解*/
class SolutionMissingNumber {
    public int missingNumber(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            // 数组下标是从0开始连续的向n增长，若相等范围区域继续向右靠
            if (nums[mid] == mid) {
                left = mid + 1;
            }
            // 不在范围区域向左靠拢
            else {
                right = mid - 1;
            }
        }
        return left;
    }
}

/*官方题解：运用的思想都是一样的*/
class SolutionMissingNumberOffer {
    public int missingNumber(int[] nums) {
        int i = 0, j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] == m) i = m + 1;
            else j = m - 1;
        }
        return i;
    }
}

/*个人思路：直接进行遍历，但这个显然不是面试官想要的结果
* 因为实在太没有技术含量了*/
class SolutionMyThinking{
    public int missingNumber(int[] nums) {
        int i;
        for (i = 0; i < nums.length; i++) {
            if (nums[i] != i){
                return i;
            }
        }
        return i;
    }
}
